package hot100;


/*
 * Author：江松
 * Date：2023/4/11 14:47
 *
 *
 分割等和子集:转化为集合中是否能取得元素，使得和为sum/2
 看成背包问题：
 分为2个集合，就是取和不取。
 f(i,j)表示前i个数，是否做到和为j
 f(i,j)=f(i-1,j)|f(i-1,j-w)


 */

public class Main416 {

    public boolean canPartition(int[] nums) {
        int n=nums.length;
        if(n<2)return false;
        int sum=0;
        for(int i:nums){
            sum+=i;
        }

        if((sum&1)!=0)return false;
        sum/=2;
        boolean dp[][]=new boolean[n+1][sum+1];
        dp[0][0]=true;
        for(int i=1;i<=n;++i){
            int w=nums[i-1];
            for(int j=1;j<=sum;++j){
                dp[i][j]=dp[i-1][j];
                if(j>=w)dp[i][j]|=dp[i-1][j-w];
            }
        }
        return dp[n][sum];
    }
}
